package _01_sort;

import org.junit.Test;

import java.util.Arrays;

import static _01_sort.SortUtil.swap;

/**
 * @author: mornd
 * @dateTime: 2023/6/22 - 18:16
 * 堆排序，选择排序的思想，不过这里使用大顶堆来查找最大值，使得查找效率变为 O(log n)
 */
public class HeapSort {
    @Test
    public void test() {
//        int[] arr = {2, 5, 4, 7, 1, 8};
        int[] arr = {1,2,3,4,5,6,7};
        heapify(arr, arr.length);
        for (int i = arr.length - 1; i > 0; i--) {
            swap(arr, 0, i);
            // 下潜第0个元素
            down(arr, 0, i);
        }
        System.out.println(Arrays.toString(arr));
    }

    private void heapify(int[] arr, int size) {
        // 套用公式 (size / 2 - 1) 可以找到最后一个非叶子节点的下标
        for (int i = size / 2 - 1; i >= 0; i--) {
            down(arr, i, size);
        }
    }

    /**
     * 下潜
     *
     * @param arr    大顶堆
     * @param parent 对顶下标
     * @param size   下潜范围
     */
    private void down(int[] arr, int parent, int size) {
        while (true) {
            int max = parent;
            int left = parent * 2 + 1; // 求出parent下标的左子树下标
            int right = left + 1;
            if (left < size && arr[left] > arr[max]) {
                max = left;
            }
            if (right < size && arr[right] > arr[max]) {
                max = right;
            }
            if (max != parent) {
                swap(arr, max, parent);
                parent = max;
            } else {
                break;
            }
        }
    }
}
